I. Field of the Invention
The present invention pertains generally to the field of wireless communications, and more particularly to generation of a broadcast challenge value in a cellular base station.
II. Background
The field of wireless communications has many applications including, e.g., cordless telephones, paging, wireless local loops, and satellite communication systems. A particularly important application is cellular telephone systems for mobile subscribers. (As used herein, the term "cellular" systems encompasses both cellular and PCS frequencies.) Various over-the-air interfaces have been developed for such cellular telephone systems including, e.g., frequency division multiple access (FDMA), time division multiple access (TDMA), and code division multiple access (CDMA). In connection therewith, various domestic and international standards have been established including, e.g., Advanced Mobile Phone Service (AMPS), Global System for Mobile (GSM), and Interim Standard 95 (IS-95). In particular, IS-95 and its derivatives, IS-95A, ANSI J-STD-008, etc. (referred to collectively herein as IS-95), are promulgated by the Telecommunication Industry Association (TIA) and other well known standards bodies.
Cellular telephone systems configured in accordance with the use of the IS-95 standard employ CDMA signal processing techniques to provide highly efficient and robust cellular telephone service. An exemplary cellular telephone system configured substantially in accordance with the use of the IS-95 standard is described in U.S. Pat. No. 5,103,459, which is assigned to the assignee of the present invention and fully incorporated herein by reference. The aforesaid patent illustrates transmit, or forward-link, signal processing in a CDMA base station. Exemplary receive, or reverse-link, signal processing in a CDMA base station is described in U.S. application Ser. No. 08/987,172, filed Dec. 9, 1997, entitled MULTICHANNEL DEMODULATOR, which is assigned to the assignee of the present invention and fully incorporated herein by reference. In CDMA systems, power control is a critical issue. An exemplary method of power control in a CDMA system is described in U.S. Pat. No. 5,056,109, which is assigned to the assignee of the present invention and fully incorporated herein by reference.
A primary benefit of using a CDMA over-the-air interface is that communications are conducted over the same RF band. For example, each mobile subscriber unit (typically a cellular telephone) in a given cellular telephone system can communicate with the same base station by transmitting a reverse link signal over the same 1.25 MHz of RF spectrum. Similarly, each base station in such a system can communicate with mobile units by transmitting a forward link signal over another 1.25 MHz of RF spectrum.
Transmitting signals over the same RF spectrum provides various benefits including, e.g., an increase in the frequency reuse of a cellular telephone system and the ability to conduct soft handoff between two or more base stations. Increased frequency reuse allows a greater number of calls to be conducted over a given amount of spectrum. Soft handoff is a robust method of transitioning a mobile unit from the coverage area of two or more base stations that involves simultaneously interfacing with two base stations. (In contrast, hard handoff involves terminating the interface with a first base station before establishing the interface with a second base station.) An exemplary method of performing soft handoff is described in U.S. Pat. No. 5,267,261, which is assigned to the assignee of the present invention and fully incorporated herein by reference.
As understood by those of skill in the art, CDMA technology can be applied to wireless local loop systems and satellite communication systems in addition to cellular systems.
In cellular telephone systems generally, mobile subscriber units, or mobile stations, must be authenticated by the base station prior to being allowed access to services such as telephone connections. Cellular communications standards typically define procedures for authentication of mobile stations using service provided by the cellular infrastructure (base stations and/or base station controllers). Cellular standards published by the TIA provide two methods for authenticating mobile stations. The methods are called the "unique challenge" method and the "broadcast challenge" method. TIA standards using these methods include IS-91 (an AMPS standard), IS-54 (a TDMA standard defining analog control channels), IS-136 (a TDMA standard defining digital control channels), and IS-95.
The unique challenge method is well known to those of skill in the art. Under the unique challenge method, the cellular infrastructure equipment sends a challenge value to a mobile station, and the mobile station sends back a response that is computed from the challenge, the mobile station identifier, and secret data known only to the base station and the legitimate mobile station having the particular identifier. If the response is correct, the cellular infrastructure provides access to services such as telephone connections. The unique challenge has the disadvantage that the time required to complete the challenge-response process can be relatively long and can unduly delay call setup. For this reason, the broadcast challenge method has been included in TIA cellular standards as a means of providing rapid authentication of requests for access to cellular services.
Under the broadcast challenge method, the challenge value (typically denoted "RAND") is broadcast on cellular control channels. A mobile station that requests access to cellular services uses the broadcast challenge value in computing a response to the challenge, the response being computed using the challenge, the mobile station identifier, and secret information known only to the base station and the mobile station with that identifier. The mobile station includes the response in its request for service.
The broadcast method can be subject to "replay" attacks in which a fraudulent mobile station monitors the communications from legitimate mobile stations and reuses both the identifier for the legitimate mobile station and the response of that station to the broadcast challenge. There exists various known methods for thwarting the replay attack. Nevertheless, a primary conventional means of thwarting replay attacks is to change the broadcast challenge value frequently. If the broadcast challenge value is changed with an update interval comparable to the duration of a typical telephone call, then replay attacks can be thwarted simply by denying accesses that appear to come from the same mobile station while a call is already in progress from that mobile station. At present, the expected duration of a cellular telephone call is approximately one minute.
However, such frequent changes of RAND can be difficult for centrally managed infrastructure equipment because the RAND value is transmitted from a large number of cell sites, and all equipment in all cell sites must be updated in order to change RAND. This places a substantial communication burden on the internal control system of the cellular infrastructure. Additionally, the updating of RAND requires that the mobile station identify which value of RAND was used to compute the response. As the mobile station may have begun its access just as an update of RAND began, it is possible for the mobile station to use the previous value of RAND rather than the updated value. Therefore, it is desirable that the cellular infrastructure not compute and accept responses for all recent values of RAND because the computation of the expected response can be slow, and because this decreases the effectiveness of RAND by increasing the likelihood that a randomly chosen response might succeed.
However, it is desirable to minimize the number of bits that must be sent on the air interface to conserve bandwidth and enhance the robustness of signaling transmission. Therefore, TIA standards for mobile station access requests typically do not include the complete value of RAND in the access request. Instead, only the most significant part of RAND is sent in the access request, thereby using a smaller number of bits to identify which RAND value was used. In TIA standards the most significant eight bits of RAND (denoted "RANDC") are used. However, this technique succeeds only if the most significant bits of RAND change each time RAND is updated. It is therefore a requirement that the RAND updating process be carried out in such a way that RANDC is distinct for each new value of RAND.
In TIA standards, RAND is typically thirty-two bits in length (bits 0 through 31), with the most significant eight bits (bits 24 through 31) being referred to as RANDC. The mobile station returns RANDC, along with its response to RAND, in access request messages. The base station must maintain a list of valid RAND values and determine, using only RANDC, which RAND value was used to compute the response returned by the mobile station. It is therefore required that all recently used RAND values have unique values of RANDC.
In addition to the above considerations pertinent to selecting RAND values, it is desirable for security reasons to maximize the period of time before a value of RAND is reused, thereby forcing a long wait before an authentication signature can be replayed. This suggests that it is not, in fact, desirable to use a truly random number for RAND. Instead, it would be desirable to use a deterministic algorithm that ensures the maximum cycle for the possible values of RAND.
Further, in most cellular systems it is disallowed to have a value of zero for RANDC because the zero value is used by the mobile station to indicate that it does not have a current value of RAND and has used all zeroes to compute the response. Hence, a characteristic of the RAND update process should be to ensure that RANDC is distinct and nonzero for each update.
Additionally, it is desirable to have successive values of RAND be as different as possible to minimize the likelihood of success for differential attacks on the response generation process. This suggests that simple, counter-based schemes are insufficient, and that updating methods with low correlation between successive values are preferable.
Finally, it is desirable to minimize messaging within the interconnection network in the cellular system by decentralizing the computation of new RAND values.
Thus, there is a need for a generation method that minimizes the correlation between successive RAND values, ensures maximum periodicity for both RAND and RANDC, and allows every cell site to perform identical updates without messaging from a central control device to trigger the update process.